#define _CRT_SECURE_NO_WARNINGS
//作者：宋安康
#include<stdio.h>
  //1、A+B
//int main() {
//    int a, b;
//    scanf("%d%d",&a,&b);
//    int c = a + b;
//    printf("%d", c);
//}

//2、01背包问题-动态规划
//f[i][j]
//1、f[i][j] = f[i-1][j]
//2、f[i][j]= f[i-1][j - v[i]] + w[i] 加上第i个的价值

//#include<stdlib.h>
////const int N = 1010;
//#define N 1010
//int n, m;
//int f[N][N];
//int v[N];
//int w[N];
//int maxL(int a, int b) 
//{
//	if (a > b) return a;
//	else
//	{
//		return b;
//	}
//}
//int main() {
//	scanf("%d%d",&n,&m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d",&v[i],&w[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++) 
//		{
//			f[i][j] = f[i - 1][j];
//			if (j >= v[i])
//				f[i][j] = maxL(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
//		}
//	}
//	int res = 0;
//	for (int i = 1; i <= m; i++)
//	{
//		res = maxL(res,f[n][i]);
//	}
//	printf("%d\n",res);
//	return 0;
//
//}

//改成一维
//const int N = 1010;
//#define N 1010
//int n, m;
//int f[N];
//int v[N];
//int w[N];
//int maxL(int a, int b) 
//{
//	if (a > b) return a;
//	else
//	{
//		return b;
//	}
//}
//int main() {
//	scanf("%d%d",&n,&m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d",&v[i],&w[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = m; j >= v[i]; j--) 
//		{
//		
//				f[j] = maxl(f[j], f[j - v[i]] + w[i]);
//		}
//	}
//	int res = 0;
//	//for (int i = 1; i <= m; i++)
//	//{
//	//	res = maxL(res,f[i]);
//	//}
//	printf("%d\n",f[m]);
//	return 0;
//
//}



//3、完全背包

//暴力算法超时
//#define N 1010
//int n, m;
//int f[N][N];
//int v[N], w[N];
//
//int main() 
//{
//	scanf("%d%d",&n,&m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d", &v[i], &w[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 0; j <= m; j++) 
//		{
//			for (int k = 0; k * v[i] <= j; k++)
//			{
//				f[i][j] = maxl(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
//			}
//		}
//	}
//	printf("%d\n",f[n][m]);
//	return 0;
//
//}

//优化
//f[i][j] = max(f[i][j-v] + w , f[i-1][j]);
//#define N 1010
//int n, m;
//int f[N][N];
//int v[N], w[N];
//
//int main() 
//{
//	scanf("%d%d",&n,&m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d", &v[i], &w[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 0; j <= m; j++) 
//		{
//			if (j >= v[i])
//			{
//				f[i][j] = maxl(f[i][j - v[i]] + w[i], f[i - 1][j]);
//			}
//			else
//				f[i][j] = f[i - 1][j];
//		}
//	}
//	printf("%d\n",f[n][m]);
//	return 0;
//
//}


//int maxl(int a, int b)
//{
//	if (a > b) return a;
//	else
//	{
//		return b;
//	}
//}
////进一步优化
//#define N 10101
//int f[N];
//int n, m;
//int v[N], w[N];
//
//int main()
//{
//	scanf("%d%d",&n,&m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d",&v[i],&w[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = v[i]; j <=  m; j++)
//		{
//			f[j] = maxl(f[j], f[j - v[i]] + w[i]);
//		}
//	}
//	printf("%d\n",f[m]);
//	return 0;
//}

//4、多重背包
//#define N 1010
//int f[N][N];
//int v[N], w[N], s[N];
//int n, m;
//
//int maxl(int a, int b)
//{
//	if (a > b) return a;
//	else
//	{
//		return b;
//	}
//}
//int main() 
//{
//	scanf("%d%d", &n, &m);
//	for (int i = 1; i <= n; i++)
//	{
//		scanf("%d%d%d",&v[i],&w[i],&s[i]);
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 0; j <= m; j++) 
//		{
//			for (int k = 0; k <= s[i]; k++)
//			{
//				if(j >= k*v[i])
//				f[i][j] = maxl(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);
//			}
//		}
//	}
//	printf("%d\n",f[n][m]);
//	return 0;
//}

//5、多重背包2
//#define N 1010
//
//int f[N]; // DP数组
//
//int maxl(int a, int b) {
//    return (a > b) ? a : b;
//}
//
//struct good {
//    int v, w; // 体积和价值
//};
//
//int main() {
//    int n, m;
//    scanf("%d%d", &n, &m);
//
//    int capacity = 10; // 初始容量
//    int size = 0;      // 当前元素数量
//
//    // 动态分配内存
//    struct good* goods = (struct good*)malloc(capacity * sizeof(struct good));
//    if (goods == NULL) {
//        printf("内存分配失败\n");
//        return 1;
//    }
//
//    // 输入物品信息
//    for (int i = 1; i <= n; i++) {
//        int v, w, s;
//        scanf("%d%d%d", &v, &w, &s); // 输入体积、价值和数量
//
//        // 多重背包分组处理
//        for (int k = 1; k <= s; k *= 2) {
//            s -= k;
//            // 扩容检查
//            if (size >= capacity) {
//                capacity *= 2;
//                goods = (struct good*)realloc(goods, capacity * sizeof(struct good));
//                if (goods == NULL) {
//                    printf("内存重新分配失败\n");
//                    return 1;
//                }
//            }
//            // 添加分组物品
//            goods[size].v = v * k;
//            goods[size].w = w * k;
//            size++;
//        }
//
//        // 处理剩余的物品
//        if (s > 0) {
//            // 扩容检查
//            if (size >= capacity) {
//                capacity *= 2;
//                goods = (struct good*)realloc(goods, capacity * sizeof(struct good));
//                if (goods == NULL) {
//                    printf("内存重新分配失败\n");
//                    return 1;
//                }
//            }
//            // 添加剩余物品
//            goods[size].v = v * s;
//            goods[size].w = w * s;
//            size++;
//        }
//    }
//
//    // 动态规划求解
//    for (int i = 0; i < size; i++) {
//        for (int j = m; j >= goods[i].v; j--) {
//            f[j] = maxl(f[j], f[j - goods[i].v] + goods[i].w);
//        }
//    }
//
//    // 输出结果
//    printf("%d\n", f[m]);
//
//    // 释放内存
//    free(goods);
//
//    return 0;
//}

//int duplicateInArray(int* nums, int numsSize) {
//	for (int i = 0; i < numsSize; i++) {
//		if (*(nums + i) < 0 || *(nums + i) >= numsSize) { return -1; }//检查非法元素    
//	}
//	for (int i = 0; i < numsSize; i++) {
//		for (int j = i + 1; j < numsSize; j++) {
//			if (*(nums + i) == *(nums + j)) { return *(nums + i); }//双层循环暴力遍历
//		}
//	}
//	return -1;
//}

//int duplicateInArray(int* nums, int numsSize) {
//	if (numsSize == 0)
//	{
//		return -1;
//	}
//	int k = 0;
//	for (int i = 0; i < numsSize/2; i++)
//	{
//		for (int j = 0; j <= numsSize; j++) 
//		{
//			if (nums[i] == nums[j] && i != j) 
//			{
//				printf("%d ",nums[i]);
//				k = 1;
//			}
//			
//		}
//	}
//	if (k == 0)
//		return -1;
//}
//
//int main() 
//{
//	int num[] = { 2, 3, 5, 4, 3, 2, 6, 7 };
//	int m = duplicateInArray(num, 8);
//	//printf("%d",m);
//	return 0;
//}